/*
 * KmpSkipSearch.cpp
 *
 *  Created on: 04-09-2013
 *      Author: Krzychu
 */

#include "KmpSkipSearch.h"

#include "Config.h"

#define ASIZE 255

KmpSkipSearch::KmpSkipSearch()
{

}

KmpSkipSearch::~KmpSkipSearch()
{

}

std::string KmpSkipSearch::getName()
{
	return "KMP Skip Search";
}

int attempt(std::string text, std::string pattern, int start, int wall)
{
	int patternSize = pattern.size();

	int k;

	k = wall - start;
	while (k < patternSize && pattern[k] == text[k + start])
	{
		++k;
	}
	return k;
}

searchResult KmpSkipSearch::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	int i, j, k, kmpStart, per, start, wall;

	/* Preprocessing */
	int* mpNext = preMp(pattern);
	int* kmpNext = preKmp(pattern);
	int* z = new int[ASIZE];
	int* list = new int[patternSize];
	z[pattern[0]] = 0;
	for (i = 1; i < patternSize; ++i)
	{
		list[i] = z[pattern[i]];
		z[pattern[i]] = i;
	}

	/* Searching */
	wall = 0;
	per = patternSize - kmpNext[patternSize];
	i = j = -1;
	do
	{
		j += patternSize;
	}
	while (j < textSize && z[text[j]] < 0);

	if (j >= textSize)
	{
		return result;
	}

	i = z[text[j]];
	start = j - i;

	while (start <= textSize - patternSize)
	{
		result.iterationsTaken++;

		if (start > wall)
		{
			wall = start;
		}

		k = attempt(text, pattern, start, wall);
		wall = start + k;
		if (k == patternSize)
		{
			result.positionsFound.push_back(start);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}
			i -= per;
		}
		else
		{
			i = list[i];
		}
		if (i < 0)
		{
			do
			{
				j += patternSize;
			}
			while (j < textSize && z[text[j]] < 0);

			if (j >= textSize)
			{
				return result;
			}
			i = z[text[j]];
		}
		kmpStart = start + k - kmpNext[k];
		k = kmpNext[k];
		start = j - i;
		while (start < kmpStart || (kmpStart < start && start < wall))
		{
			if (start < kmpStart)
			{
				i = list[i];
				if (i < 0)
				{
					do
					{
						j += patternSize;
					}
					while (j < textSize && z[text[j]] < 0);

					if (j >= textSize)
					{
						return result;
					}
					i = z[text[j]];
				}
				start = j - i;
			}
			else
			{
				kmpStart += (k - mpNext[k]);
				k = mpNext[k];
			}
		}
	}

	return result;
}

